package visualizer.client.algorithms;

import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:58
 */
public class DSWAlgorithm implements Algorithm {
    private int totalStepCount;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return balance(tree.copyTree(false), step);
    }

    @Override
    public int getStepsCount(BinaryTree tree, int inputValue) {
        totalStepCount = 0;
        balance(tree.copyTree(false), -1);
        return totalStepCount;
    }

    private AlgoResult balance(BinaryTree tree, int step) {
        if (step-- == 0) {
            return new AlgoResult(tree, "Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, т.е. чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. " +
                    "В противном случае теряется производительность. " +
                    "В идеально сбалансированном дереве поиск узла занимает О(log n) времени.");
        }
        if (step-- == 0) {
            return new AlgoResult(tree, "Алгоритм Day–Stout–Warren (DSW) состоит из 2 частей: построения лозы и ее последующего преобразования. " +
                    "Все преобразования выполняются ротациями.");
        }
        if (step-- == 0) {
            return new AlgoResult(tree, "Для построения лозы будем проверять на наличие у узла левого потомка. " +
                    "Если он есть - выполняем ротацию вправо относительно данного узла и переходим к рассмотрению этого потомка. " +
                    "Если левое поддерево пусто, то переходим к рассмотрению правого потомка.");
        }
        //построение лозы
        BNode root = tree.getRoot();
        for (BNode p = root; p != null; p = p.getRightBNode()) {
            do {
                if (step-- == 0) {
                    p.setOuterColor("red");
                    return new AlgoResult(tree, "Переходим к рассмотрению узла " + p.getValue());
                }
                if (p.getLeftBNode() != null) {
                    AlgoResult res = getPreRightRotateAlgoResult(tree, p);
                    if (step == 0 || step == 1) {
                        p.setOuterColor("red");
                        p.getLeftBNode().setOuterColor("green");
                    }
                    if (step-- == 0) {
                        return res;
                    }
                    rightRotate(p);
                    if (step-- == 0) {
                        return res;
                    }
                } else {
                    if (step-- == 0) {
                        p.setOuterColor("red");
                        return new AlgoResult(tree, "У узла " + p.getValue() + " нет левого потомка");
                    }
                }
            } while (p.getLeftBNode() != null);
        }

        if (step-- == 0) {
            return new AlgoResult(tree, "Построение лозы закончено. Переходим к построению сбалансированного дерева.");
        }

        //балансировка лозы
        for (int i = countNodes(root) / 2; i > 0; i /= 2) {
            int k = 0;
            for (BNode p = root; k < i; ++k, p = p.getRightBNode()) {
                if (step-- == 0) {
                    p.setOuterColor("green");
                    return new AlgoResult(tree, "Выполняем ротацию влево для узла " + p.getValue());
                }
                leftRotate(p);
                if (step-- == 0) {
                    p.getLeftBNode().setOuterColor("green");
                    return new AlgoResult(tree, "Выполняем ротацию влево для узла " + p.getLeftBNode().getValue());
                }
            }
        }
        updateTotalStepCount(step);
        return new AlgoResult(tree, "Алгоритм балансировки бинарного дерева DSW закончен");
    }

    private AlgoResult getPreRightRotateAlgoResult(BinaryTree tree, BNode p) {
        return new AlgoResult(tree, "Узел " + p.getLeftBNode().getValue() + " является левым потомком узла " + p.getValue() + "." +
                                " Необходимо выполнить ротацию вправо, сделав узел " + p.getValue() +
                                " правым потомком узла " + p.getLeftBNode().getValue() +
                                ". Правое поддерево узла " + p.getLeftBNode().getValue() + " станет левым поддеревом узла " + p.getValue() + ".");
    }

    private void leftRotate(BNode n) {
        if (n.getRightBNode() != null) {
            BNode rightBNode = n.getRightBNode();
            n.setRightBNode(rightBNode.getRightBNode());
            rightBNode.setRightBNode(rightBNode.getLeftBNode());
            rightBNode.setLeftBNode(n.getLeftBNode());
            n.setLeftBNode(rightBNode);

            swapData(n, rightBNode);
        }
    }

    private void rightRotate(BNode node) {
        if (node.getLeftBNode() != null) {
            BNode leftBNode = node.getLeftBNode();
            node.setLeftBNode(leftBNode.getLeftBNode());
            leftBNode.setLeftBNode(leftBNode.getRightBNode());
            leftBNode.setRightBNode(node.getRightBNode());
            node.setRightBNode(leftBNode);

            swapData(node, leftBNode);
        }
    }

    private void swapData(BNode node1, BNode node2) {
        int temp = node1.getValue();
        node1.setValue(node2.getValue());
        node2.setValue(temp);

        String innerColor = node1.getInnerColor();
        node1.setInnerColor(node2.getInnerColor());
        node2.setInnerColor(innerColor);

        String outerColor = node1.getOuterColor();
        node1.setOuterColor(node2.getOuterColor());
        node2.setOuterColor(outerColor);
    }

    private int countNodes(BNode root) {
        if (root == null) {
            return 0;
        }
        int i = 1;
        while (root.getRightBNode() != null) {
            root = root.getRightBNode();
            i++;
        }
        return i;
    }

    private void updateTotalStepCount(int stepNo) {
        if (stepNo < 0) {
            totalStepCount = -stepNo;
        }
    }
}
